package algorithm.swordoff;

/**
 * 二叉搜索树与双向链表
 */

public class SQ36 {

    Node pre, head;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        inorder(root);

        // 首尾单独操作
        head.left = pre;
        pre.right = head;

        return head;

    }

    public void inorder(Node curr) {
        if (curr == null) return;

        inorder(curr.left);

        // 中序遍历操作: 如果pre是空表示当前节点为头节点,否则pre和curr左右相连,pre指向curr
        if (pre == null) head = curr;
        else pre.right = curr;
        curr.left = pre;
        pre = curr;

        inorder(curr.right);
    }

}


class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}